package mergeTwoLists21;

public class MergeTwoLists {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //递归
        if (l1 == null) {
            return l2;
        }else if (l2 == null) {
            return l1;
        }else if(l1.val<l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else if(l1.val>l2.val){
            l2.next = mergeTwoLists(l2.next,l1);
            return l2;
        }else{
            return l1;
        }
    }


    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        //比较迭代，因为二者都是有序，所以新构件一个链表，用于保存l1和l2每个节点比较出最小的。当有一个链表为null时，将另一个链表比较剩下的拼接后面
        ListNode node = new ListNode();
        //ListNode node = root;
        while (l1!=null && l2!=null){
            if(l1.val<l2.val){
                node.next = l1;
                l1 = l1.next;
            }else{
                node.next = l2;
                l2 = l2.next;
            }
            //不停的给node赋值，所以node也要继续向后移动
            node = node.next;
        }
        //当有一个链表为null时，将另一个链表比较剩下的拼接后面
        node.next = l2 == null?l1:l2;
        return node;
    }



}
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}